package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.DynamicProblem;

import java.util.Arrays;

/**
 * 硬币找零 动态规划
 * https://leetcode.com/problems/coin-change/
 *
 * @author tzp
 * @since 2020/9/11
 */
public class LC322 implements DynamicProblem {
    public static void main(String[] args) {
        System.out.println(new LC322().coinChange(new int[]{2}, 3));
        System.out.println(new LC322().coinChange(new int[]{2, 5, 7}, 27));
    }

    public int coinChange(int[] coins, int amount) {
        int[] cache = new int[amount + 1];
        Arrays.fill(cache, -2);//-2表示没算过, -1表示无解
        cache[0] = 0;
        re(coins, amount, cache);
        return cache[amount];
    }

    public void re(int[] coins, int amount, int[] cache) {
        if (cache[amount] != -2) {
            return;
        }
        int least = Integer.MAX_VALUE;
        for (int coin : coins) {
            if (coin <= amount) {
                re(coins, amount - coin, cache);
                if (cache[amount - coin] == -1) {
                    continue;
                }
                if (cache[amount - coin] < least) {
                    least = cache[amount - coin];
                }
            }
        }
        if (least == Integer.MAX_VALUE) {
            cache[amount] = -1;
        } else {
            cache[amount] = least + 1;
        }
    }
}
